package book;

public class NumTowerSolution {
    // 计算数塔的最小路径和
    public int minimumTotal(int[][] triangle) {
        int n = triangle.length;
        // 创建备忘录
        int[][] dp = new int[n][n];
        // 自下而上进行填表
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                if (i == n - 1)
                    dp[i][j] = triangle[i][j];
                else
                    dp[i][j] = triangle[i][j] + 
                        Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        // 完成填表并返回结果
        return dp[0][0];
    }
    public static void main(String[] args) {
        int[][] triangle = 
            { { 9 },
            { 13, 16 },
           { 4, 10, 7 },
         { 9, 11, 6, 13 },
        { 17, 5, 19, 11, 10}};
        int ans = new NumTowerSolution().minimumTotal(triangle);
        System.out.println("最小路径和为: " + ans);
    }
}
